/*
https://leetcode.cn/problems/coin-bonus/solution/xiao-ai-lao-shi-li-kou-bei-li-jie-zhen-t-rut3/
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolutionLCP5 {

    public static final long mod=1000000007;

    static class Bit{

        int n;
        long[] h;

        public Bit(int n){
            h=new long[n+1];
            this.n=n;
        }

        public long query(int x){
            long ans=0;
            while (x>0){
                ans=(ans+h[x])%mod;
                x-=lowbit(x);
            }
            return ans;
        }

        public void update(int x,long d){
            while (x<=n){
                h[x]=(h[x]+d)%mod;
                x+=lowbit(x);
            }
        }

        private int lowbit(int x) {
            return x&(-x);
        }
    }

    int id=0;

    public int[] bonus(int n, int[][] leadership, int[][] operations) {
        int[] first=new int[n+1];
        Arrays.fill(first,-1);
        int[] next=new int[leadership.length];
        int[] go=new int[leadership.length];
        for (int i=0;i<leadership.length;i++) {
            next[i]=first[leadership[i][0]];
            first[leadership[i][0]]=i;
            go[i]=leadership[i][1];
        }
        int[] begin=new int[n+1];
        int[] end=new int[n+1];
        dfs(1,first,next,go,begin,end);
        List<Integer> list=new ArrayList<>();
        Bit b1=new Bit(n);
        Bit b2=new Bit(n);
        for (int[] operation : operations) {
            if (operation[0]==1){
                b1.update(begin[operation[1]],operation[2]);
                b1.update(begin[operation[1]]+1,-operation[2]);
                b2.update(begin[operation[1]], (long)begin[operation[1]]*operation[2]);
                b2.update(begin[operation[1]]+1,(long)-(begin[operation[1]]+1)*operation[2]);
            }else if (operation[0]==2){
                b1.update(begin[operation[1]],operation[2]);
                b1.update(end[operation[1]]+1,-operation[2]);
                b2.update(begin[operation[1]],(long)begin[operation[1]]*operation[2]);
                b2.update(end[operation[1]]+1,(long)-(end[operation[1]]+1)*operation[2]);
            }else {
                long a1=(b1.query(end[operation[1]]))*(end[operation[1]]+1)-b2.query(end[operation[1]]);
                long a2=(b1.query(begin[operation[1]]-1))*begin[operation[1]]-b2.query(begin[operation[1]]-1);
                list.add((int)((a1-a2+mod)%mod));
            }
        }
        int[] ans=new int[list.size()];
        for (int i=0;i<ans.length;i++){
            ans[i]=list.get(i);
        }
        return ans;
    }

    private void dfs(int k, int[] first, int[] next, int[] go, int[] begin, int[] end) {
        id++;
        begin[k]=id;
        int v=first[k];
        while (v!=-1){
            dfs(go[v],first,next,go,begin,end);
            v=next[v];
        }
        end[k]=id;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionLCP5().bonus(6, new int[][]{{1, 2}, {1, 6}, {2, 3}, {2, 5}, {1, 4}}, new int[][]{{1, 1, 500}, {2, 2, 50}, {3, 1}, {2, 6, 15}, {3, 1}})));
    }
}
